/*
===========================================================================
Copyright (C) 1999-2005 Id Software, Inc.

This file is part of Quake III Arena source code.

Quake III Arena source code is free software; you can redistribute it
and/or modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of the License,
or (at your option) any later version.

Quake III Arena source code is distributed in the hope that it will be
useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with Foobar; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
===========================================================================
*/

#include "qbsp.h"
#include "../common/aselib.h"
#ifdef _WIN32
#ifdef _TTIMOBUILD
#include "pakstuff.h"
#else
#include "../libs/pakstuff.h"
#endif
#endif


typedef struct {
	char		modelName[256];
	md3Header_t	*header;
} loadedModel_t;

int		c_triangleModels;
int		c_triangleSurfaces;
int		c_triangleVertexes;
int		c_triangleIndexes;


#define	MAX_LOADED_MODELS	4096
loadedModel_t		loadedModels[MAX_LOADED_MODELS];
int					numLoadedModels;

/*
=================
R_LoadMD3
=================
*/
#define	LL(x) x=LittleLong(x)
md3Header_t *R_LoadMD3( const char *mod_name ) {
	int					i, j;
	md3Header_t			*md3;
    md3Frame_t			*frame;
	md3Surface_t		*surf;
	md3Triangle_t		*tri;
	md3St_t				*st;
	md3XyzNormal_t		*xyz;
	int					version;
	char				filename[1024];
	int					len;

	sprintf( filename, "%s%s", gamedir, mod_name );
	len = TryLoadFile( filename, (void **)&md3 );
#ifdef _WIN32
  if ( len <= 0 ) {
    len = PakLoadAnyFile(filename, (void **)&md3);
  }
#endif
	if ( len <= 0 ) {
	  return NULL;
	}

  version = LittleLong (md3->version);
	if (version != MD3_VERSION) {
		_printf( "R_LoadMD3: %s has wrong version (%i should be %i)\n",
				 mod_name, version, MD3_VERSION);
		return NULL;
	}

    LL(md3->ident);
    LL(md3->version);
    LL(md3->numFrames);
    LL(md3->numTags);
    LL(md3->numSurfaces);
    LL(md3->numSkins);
    LL(md3->ofsFrames);
    LL(md3->ofsTags);
    LL(md3->ofsSurfaces);
    LL(md3->ofsEnd);

	if ( md3->numFrames < 1 ) {
		_printf( "R_LoadMD3: %s has no frames\n", mod_name );
		return NULL;
	}

    // we don't need to swap tags in the renderer, they aren't used
    
	// swap all the frames
    frame = (md3Frame_t *) ( (byte *)md3 + md3->ofsFrames );
    for ( i = 0 ; i < md3->numFrames ; i++, frame++) {
    	frame->radius = LittleFloat( frame->radius );
        for ( j = 0 ; j < 3 ; j++ ) {
            frame->bounds[0][j] = LittleFloat( frame->bounds[0][j] );
            frame->bounds[1][j] = LittleFloat( frame->bounds[1][j] );
	    	frame->localOrigin[j] = LittleFloat( frame->localOrigin[j] );
        }
	}

	// swap all the surfaces
	surf = (md3Surface_t *) ( (byte *)md3 + md3->ofsSurfaces );
	for ( i = 0 ; i < md3->numSurfaces ; i++) {

        LL(surf->ident);
        LL(surf->flags);
        LL(surf->numFrames);
        LL(surf->numShaders);
        LL(surf->numTriangles);
        LL(surf->ofsTriangles);
        LL(surf->numVerts);
        LL(surf->ofsShaders);
        LL(surf->ofsSt);
        LL(surf->ofsXyzNormals);
        LL(surf->ofsEnd);
		
		if ( surf->numVerts > SHADER_MAX_VERTEXES ) {
			Error ("R_LoadMD3: %s has more than %i verts on a surface (%i)",
				mod_name, SHADER_MAX_VERTEXES, surf->numVerts );
		}
		if ( surf->numTriangles*3 > SHADER_MAX_INDEXES ) {
			Error ("R_LoadMD3: %s has more than %i triangles on a surface (%i)",
				mod_name, SHADER_MAX_INDEXES / 3, surf->numTriangles );
		}

		// swap all the triangles
		tri = (md3Triangle_t *) ( (byte *)surf + surf->ofsTriangles );
		for ( j = 0 ; j < surf->numTriangles ; j++, tri++ ) {
			LL(tri->indexes[0]);
			LL(tri->indexes[1]);
			LL(tri->indexes[2]);
		}

		// swap all the ST
        st = (md3St_t *) ( (byte *)surf + surf->ofsSt );
        for ( j = 0 ; j < surf->numVerts ; j++, st++ ) {
            st->st[0] = LittleFloat( st->st[0] );
            st->st[1] = LittleFloat( st->st[1] );
        }

		// swap all the XyzNormals
        xyz = (md3XyzNormal_t *) ( (byte *)surf + surf->ofsXyzNormals );
        for ( j = 0 ; j < surf->numVerts * surf->numFrames ; j++, xyz++ ) 
		{
            xyz->xyz[0] = LittleShort( xyz->xyz[0] );
            xyz->xyz[1] = LittleShort( xyz->xyz[1] );
            xyz->xyz[2] = LittleShort( xyz->xyz[2] );

            xyz->normal = LittleShort( xyz->normal );
        }


		// find the next surface
		surf = (md3Surface_t *)( (byte *)surf + surf->ofsEnd );
	}

	return md3;
}


/*
================
LoadModel
================
*/
md3Header_t *LoadModel( const char *modelName ) {
	int				i;
	loadedModel_t	*lm;

	// see if we already have it loaded
	for ( i = 0, lm = loadedModels ; i < numLoadedModels ; i++, lm++ ) {
		if ( !strcmp( modelName, lm->modelName ) ) {
			return lm->header;
		}
	}

	// load it
	if ( numLoadedModels == MAX_LOADED_MODELS ) {
		Error( "MAX_LOADED_MODELS" );
	}
	numLoadedModels++;

	strcpy( lm->modelName, modelName );

	lm->header = R_LoadMD3( modelName );

	return lm->header;
}


// =====================================================================


/*
============
InsertMD3Model

Convert a model entity to raw geometry surfaces and insert it in the tree
============
*/
void InsertMD3Model( const char *modelName, vec3_t origin, vec3_t axis[3], const char *clipModel ) {
	int					i, j;
	md3Header_t			*md3;
	md3Surface_t		*surf;
	md3Shader_t			*shader;
	md3Triangle_t		*tri;
	md3St_t				*st;
	md3XyzNormal_t		*xyz;
	drawVert_t			*outv;
	float				lat, lng;
	mapDrawSurface_t	*out;
	vec3_t				temp;
	char				material[256];

	// load the model
	md3 = LoadModel( modelName );
	if ( !md3 ) {
		return;
	}

	// each md3 surface will become a new bsp surface

	c_triangleModels++;
	c_triangleSurfaces += md3->numSurfaces;

	// expand, translate, and rotate the vertexes
	// swap all the surfaces
	surf = (md3Surface_t *) ( (byte *)md3 + md3->ofsSurfaces );
	for ( i = 0 ; i < md3->numSurfaces ; i++) {
		// allocate a surface
		out = AllocDrawSurf();
		out->terrain = qfalse;
		out->miscModel = qtrue;
		out->clipModel = (clipModel[0]) ? qtrue : qfalse;
		strcpy(out->clipModelName, clipModel);
		out->clipModelSurface = i;
		VectorCopy(origin, out->clipModelOrigin);
		VectorCopy(axis[0], out->clipModelAxis[0]);
		VectorCopy(axis[1], out->clipModelAxis[1]);
		VectorCopy(axis[2], out->clipModelAxis[2]);

        shader = (md3Shader_t *) ( (byte *)surf + surf->ofsShaders );

		strcpy(material, shader->name);
		if (strchr(material, '.'))
			*strchr(material, '.') = 0;

		out->shaderInfo = ShaderInfoForShader( material );

		out->numVerts = surf->numVerts;
		out->verts = malloc( out->numVerts * sizeof( out->verts[0] ) );

		out->numIndexes = surf->numTriangles * 3;
		out->indexes = malloc( out->numIndexes * sizeof( out->indexes[0] ) );

		// emit the indexes
		c_triangleIndexes += surf->numTriangles * 3;
		tri = (md3Triangle_t *) ( (byte *)surf + surf->ofsTriangles );
		for ( j = 0 ; j < surf->numTriangles ; j++, tri++ ) {
			out->indexes[j*3+0] = tri->indexes[0];
			out->indexes[j*3+1] = tri->indexes[1];
			out->indexes[j*3+2] = tri->indexes[2];
		}

		// emit the vertexes
        st = (md3St_t *) ( (byte *)surf + surf->ofsSt );
        xyz = (md3XyzNormal_t *) ( (byte *)surf + surf->ofsXyzNormals );

		c_triangleVertexes += surf->numVerts;
		for ( j = 0 ; j < surf->numVerts ; j++, st++, xyz++ ) {
			outv = &out->verts[ j ];

			outv->st[0] = st->st[0];
			outv->st[1] = st->st[1];

			temp[0] = MD3_XYZ_SCALE * xyz->xyz[0];
			temp[1] = MD3_XYZ_SCALE * xyz->xyz[1];
			temp[2] = MD3_XYZ_SCALE * xyz->xyz[2];

			outv->xyz[0] = DotProduct(temp, axis[0]) + origin[0];
			outv->xyz[1] = DotProduct(temp, axis[1]) + origin[1];
			outv->xyz[2] = DotProduct(temp, axis[2]) + origin[2];

			// decode the lat/lng normal to a 3 float normal
			lat = ( xyz->normal >> 8 ) & 0xff;
			lng = ( xyz->normal & 0xff );
			lat *= Q_PI/128;
			lng *= Q_PI/128;

			temp[0] = cos(lat) * sin(lng);
			temp[1] = sin(lat) * sin(lng);
			temp[2] = cos(lng);

			// rotate the normal
			outv->normal[0] = DotProduct(temp, axis[0]);
			outv->normal[1] = DotProduct(temp, axis[1]);
			outv->normal[2] = DotProduct(temp, axis[2]);

			outv->color[0] = 255;
			outv->color[1] = 255;
			outv->color[2] = 255;
			outv->color[3] = 255;
		}

		// find the next surface
		surf = (md3Surface_t *)( (byte *)surf + surf->ofsEnd );
	}

}

//==============================================================================


/*
============
InsertASEModel

Convert a model entity to raw geometry surfaces and insert it in the tree
============
*/
void InsertASEModel( const char *modelName, vec3_t origin, vec3_t axis[3], const char *clipModel ) {
	int					i, j, l;
	mapDrawSurface_t	*out;
	int					numSurfaces;
	const char			*name;
	polyset_t			*pset;
	int					numFrames;
	char				filename[1024];
	char				material[256];

	int					indexList[SHADER_MAX_INDEXES];
	int					numIndices;

	drawVert_t			vertexList[SHADER_MAX_VERTEXES], vertex;
	int					numVertices;

	sprintf( filename, "%s%s", gamedir, modelName );

	// load the model
	ASE_Load( filename, qfalse, qfalse );

	// each ase surface will become a new bsp surface
	numSurfaces = ASE_GetNumSurfaces();

	c_triangleModels++;
	c_triangleSurfaces += numSurfaces;

	// expand, translate, and rotate the vertexes
	// swap all the surfaces
	for ( i = 0 ; i < numSurfaces ; i++) {
		name = ASE_GetSurfaceName( i );

		pset = ASE_GetSurfaceAnimation( i, &numFrames, -1, -1, -1 );
		if ( !name || !pset ) {
			continue;
		}

		// allocate a surface
		out = AllocDrawSurf();
		out->terrain = qfalse;
		out->miscModel = qtrue;
		out->clipModel = (clipModel[0]) ? qtrue : qfalse;
		strcpy(out->clipModelName, clipModel);
		out->clipModelSurface = i;
		VectorCopy(origin, out->clipModelOrigin);
		VectorCopy(axis[0], out->clipModelAxis[0]);
		VectorCopy(axis[1], out->clipModelAxis[1]);
		VectorCopy(axis[2], out->clipModelAxis[2]);

		strcpy(material, pset->materialname);
		if (strchr(material, '.'))
			*strchr(material, '.') = 0;

		out->shaderInfo = ShaderInfoForShader( material );

		// Copy vertices
		numIndices = 0;
		numVertices = 0;

		for ( j = 0 ; j < pset->numtriangles * 3 ; j++ ) {
			int		index;
			triangle_t	*tri;

			index = j % 3;
			tri = &pset->triangles[ j / 3 ];

			vertex.st[0] = tri->texcoords[index][0];
			vertex.st[1] = tri->texcoords[index][1];

			vertex.xyz[0] = tri->verts[index][0];
			vertex.xyz[1] = tri->verts[index][1];
			vertex.xyz[2] = tri->verts[index][2];

			vertex.color[0] = (byte)(255.0f * tri->colors[index][0]);
			vertex.color[1] = (byte)(255.0f * tri->colors[index][1]);
			vertex.color[2] = (byte)(255.0f * tri->colors[index][2]);
			vertex.color[3] = 255;

			// Add it to the vertex list if not added yet
			if (numIndices == SHADER_MAX_INDEXES){
				printf("SHADER_MAX_INDEXES hit\n");
				return;
			}

			for (l = 0; l < numVertices; l++){
				if (vertexList[l].xyz[0] != vertex.xyz[0] || vertexList[l].xyz[1] != vertex.xyz[1] || vertexList[l].xyz[2] != vertex.xyz[2])
					continue;
				if (vertexList[i].st[0] != vertex.st[0] || vertexList[i].st[1] != vertex.st[1])
					continue;

				break;
			}

			if (l == numVertices){
				if (numVertices == SHADER_MAX_VERTEXES){
					printf("SHADER_MAX_VERTEXES hit\n");
					return;
				}

				indexList[numIndices++] = numVertices;
				vertexList[numVertices++] = vertex;
			}
			else
				indexList[numIndices++] = l;
		}

		// Emit the indices
		out->numIndexes = numIndices;
		out->indexes = malloc(out->numIndexes * sizeof(out->indexes[0]));

		c_triangleIndexes += numIndices;

		for (j = 0; j < numIndices; j += 3){
			out->indexes[j+0] = indexList[j+0];
			out->indexes[j+1] = indexList[j+1];
			out->indexes[j+2] = indexList[j+2];
		}

		// Emit the vertices
		out->numVerts = numVertices;
		out->verts = malloc(out->numVerts * sizeof(out->verts[0]));

		c_triangleVertexes += numVertices;

		for (j = 0; j < numVertices; j++){
			out->verts[j].xyz[0] = DotProduct(vertexList[j].xyz, axis[0]) + origin[0];
			out->verts[j].xyz[1] = DotProduct(vertexList[j].xyz, axis[1]) + origin[1];
			out->verts[j].xyz[2] = DotProduct(vertexList[j].xyz, axis[2]) + origin[2];

			out->verts[j].st[0] = vertexList[j].st[0];
			out->verts[j].st[1] = vertexList[j].st[1];

			out->verts[j].color[0] = vertexList[j].color[0];
			out->verts[j].color[1] = vertexList[j].color[1];
			out->verts[j].color[2] = vertexList[j].color[2];
			out->verts[j].color[3] = vertexList[j].color[3];
		}
	}

}


//==============================================================================


/*
 =================
 InsertLWOModel

 Convert a model entity to raw geometry surfaces and insert it in the tree
 =================
*/
void InsertLWOModel  (const char *modelName, vec3_t origin, vec3_t axis[3], const char *clipModel){

	lwObject			*inObject;
	lwLayer				*inLayer;
	lwSurface			*inSurface;
	lwPolygon			*inPolygon;
	lwPolVert			*inPolVert;
	lwPoint				*inPoint;
	lwVMapPt			*inVMapPt;
	mapDrawSurface_t	*out;
	char				material[256];
	int					defaultSTAxis[2];
	float				defaultXYZ2STScale[2];
	float				min, max, size, st[2];
	unsigned			failId;
	int					failPos;
	int					i, j, k, l;

	int					indexList[SHADER_MAX_INDEXES];
	int					numIndices;

	drawVert_t			vertexList[SHADER_MAX_VERTEXES], vertex;
	int					numVertices;

	char				filename[1024];

	sprintf( filename, "%s%s", gamedir, modelName );

	// Load the file
	inObject = lwGetObject(filename, &failId, &failPos);
	if (!inObject){
		printf("Couldn't find %s\n", modelName);
		return;
	}

	if (inObject->nlayers != 1){
		printf("LWO has invalid number of layers (%i)\n", inObject->nlayers);
		return;
	}

	inLayer = &inObject->layer[0];

	// Setup default ST map
	defaultSTAxis[0] = 0;
	defaultSTAxis[1] = 1;

	st[0] = 0.0f;
	st[1] = 0.0f;

	for (i = 0; i < 3; i++){
		min = inLayer->bbox[i+0];
		max = inLayer->bbox[i+3];

		size = max - min;

		if (size > st[0]){
			defaultSTAxis[1] = defaultSTAxis[0];
			defaultSTAxis[0] = i;

			st[1] = st[0];
			st[0] = size;
		}
		else if (size > st[1]){
			defaultSTAxis[1] = i;

			st[1] = size;
		}
	}

	defaultXYZ2STScale[0] = 4.0f / st[0];
	defaultXYZ2STScale[1] = 4.0f / st[1];

	// Each LWO surface will become a new BSP surface
	c_triangleModels++;
	c_triangleSurfaces += inObject->nsurfs;

	inSurface = inObject->surf;

	for (i = 0; i < inObject->nsurfs; i++){
		// Allocate a surface
		out = AllocDrawSurf();
		out->terrain = qfalse;
		out->miscModel = qtrue;
		out->clipModel = (clipModel[0]) ? qtrue : qfalse;
		strcpy(out->clipModelName, clipModel);
		out->clipModelSurface = i;
		VectorCopy(origin, out->clipModelOrigin);
		VectorCopy(axis[0], out->clipModelAxis[0]);
		VectorCopy(axis[1], out->clipModelAxis[1]);
		VectorCopy(axis[2], out->clipModelAxis[2]);

		// Copy the material
		strcpy(material, inSurface->name);
		if (strchr(material, '.'))
			*strchr(material, '.') = 0;

		out->shaderInfo = ShaderInfoForShader(material);

		// Copy vertices
		numIndices = 0;
		numVertices = 0;

		for (j = 0, inPolygon = inLayer->polygon.pol; j < inLayer->polygon.count; j++, inPolygon++){
			if (inPolygon->surf != inSurface)
				continue;

			if (inPolygon->type != ID_FACE){
				qprintf("WARNING: polygon type != ID_FACE, discarded...\n");
				continue;
			}

			if (inPolygon->nverts != 3){
				qprintf("WARNING: polygon has %i vertices, discarded...\n", inPolygon->nverts);
				continue;
			}

			for (k = 0, inPolVert = inPolygon->v; k < 3; k++, inPolVert++){
				inPoint = &inLayer->point.pt[inPolVert->index];

				vertex.xyz[0] = inPoint->pos[0];
				vertex.xyz[1] = inPoint->pos[2];
				vertex.xyz[2] = inPoint->pos[1];

				vertex.st[0] = vertex.xyz[defaultSTAxis[0]] * defaultXYZ2STScale[0];
				vertex.st[1] = vertex.xyz[defaultSTAxis[1]] * defaultXYZ2STScale[1];

				vertex.color[0] = inSurface->color.rgb[0] * inSurface->diffuse.val * 255;
				vertex.color[1] = inSurface->color.rgb[1] * inSurface->diffuse.val * 255;
				vertex.color[2] = inSurface->color.rgb[2] * inSurface->diffuse.val * 255;
				vertex.color[3] = 255;

				for (l = 0, inVMapPt = inPoint->vm; l < inPoint->nvmaps; l++, inVMapPt++){
					if (inVMapPt->vmap->type == LWID_('T', 'X', 'U', 'V')){
						vertex.st[0] = inVMapPt->vmap->val[inVMapPt->index][0];
						vertex.st[1] = 1.0f - inVMapPt->vmap->val[inVMapPt->index][1];
					}

					if (inVMapPt->vmap->type == LWID_('R', 'G', 'B', 'A')){
						vertex.color[0] = inVMapPt->vmap->val[inVMapPt->index][0] * inSurface->color.rgb[0] * inSurface->diffuse.val * 255;
						vertex.color[1] = inVMapPt->vmap->val[inVMapPt->index][1] * inSurface->color.rgb[1] * inSurface->diffuse.val * 255;
						vertex.color[2] = inVMapPt->vmap->val[inVMapPt->index][2] * inSurface->color.rgb[2] * inSurface->diffuse.val * 255;
						vertex.color[3] = inVMapPt->vmap->val[inVMapPt->index][3] * 255;
					}
				}

				for (l = 0, inVMapPt = inPolVert->vm; l < inPolVert->nvmaps; l++, inVMapPt++){
					if (inVMapPt->vmap->type == LWID_('T', 'X', 'U', 'V')){
						vertex.st[0] = inVMapPt->vmap->val[inVMapPt->index][0];
						vertex.st[1] = 1.0f - inVMapPt->vmap->val[inVMapPt->index][1];
					}

					if (inVMapPt->vmap->type == LWID_('R', 'G', 'B', 'A')){
						vertex.color[0] = inVMapPt->vmap->val[inVMapPt->index][0] * inSurface->color.rgb[0] * inSurface->diffuse.val * 255;
						vertex.color[1] = inVMapPt->vmap->val[inVMapPt->index][1] * inSurface->color.rgb[1] * inSurface->diffuse.val * 255;
						vertex.color[2] = inVMapPt->vmap->val[inVMapPt->index][2] * inSurface->color.rgb[2] * inSurface->diffuse.val * 255;
						vertex.color[3] = inVMapPt->vmap->val[inVMapPt->index][3] * 255;
					}
				}

				// Add it to the vertex list if not added yet
				if (numIndices == SHADER_MAX_INDEXES){
					printf("SHADER_MAX_INDEXES hit\n");
					return;
				}

				for (l = 0; l < numVertices; l++){
					if (vertexList[l].xyz[0] != vertex.xyz[0] || vertexList[l].xyz[1] != vertex.xyz[1] || vertexList[l].xyz[2] != vertex.xyz[2])
						continue;
					if (vertexList[i].st[0] != vertex.st[0] || vertexList[i].st[1] != vertex.st[1])
						continue;

					break;
				}

				if (l == numVertices){
					if (numVertices == SHADER_MAX_VERTEXES){
						printf("SHADER_MAX_VERTEXES hit\n");
						return;
					}

					indexList[numIndices++] = numVertices;
					vertexList[numVertices++] = vertex;
				}
				else
					indexList[numIndices++] = l;
			}
		}

		// Emit the indices
		out->numIndexes = numIndices;
		out->indexes = malloc(out->numIndexes * sizeof(out->indexes[0]));

		c_triangleIndexes += numIndices;

		for (j = 0; j < numIndices; j += 3){
			out->indexes[j+0] = indexList[j+0];
			out->indexes[j+1] = indexList[j+1];
			out->indexes[j+2] = indexList[j+2];
		}

		// Emit the vertices
		out->numVerts = numVertices;
		out->verts = malloc(out->numVerts * sizeof(out->verts[0]));

		c_triangleVertexes += numVertices;

		for (j = 0; j < numVertices; j++){
			out->verts[j].xyz[0] = DotProduct(vertexList[j].xyz, axis[0]) + origin[0];
			out->verts[j].xyz[1] = DotProduct(vertexList[j].xyz, axis[1]) + origin[1];
			out->verts[j].xyz[2] = DotProduct(vertexList[j].xyz, axis[2]) + origin[2];

			out->verts[j].st[0] = vertexList[j].st[0];
			out->verts[j].st[1] = vertexList[j].st[1];

			out->verts[j].color[0] = vertexList[j].color[0];
			out->verts[j].color[1] = vertexList[j].color[1];
			out->verts[j].color[2] = vertexList[j].color[2];
			out->verts[j].color[3] = vertexList[j].color[3];
		}

		// Skip to next surface
		inSurface = inSurface->next;
	}

	lwFreeObject(inObject);
}


//==============================================================================



/*
=====================
AddTriangleModels
=====================
*/
void AddTriangleModels( entity_t *e, tree_t *tree ) {
	int			entity_num;
	entity_t	*entity;
	vec3_t		axis[3];
//	const char	*parentName, *parent;
	const char	*clipModel;

	if (noModelBrushes)
		return;

	qprintf("----- AddTriangleModels -----\n");

//	if (e == entities)
//		parentName = "";
//	else
//		parentName = ValueForKey(e, "name");

	for ( entity_num=1 ; entity_num< num_entities ; entity_num++ ) {
		entity = &entities[entity_num];
	
		// convert func_statics into raw geometry
		if ( !Q_stricmp( "func_static", ValueForKey( entity, "classname" ) ) ) {
			const char	*model;
			vec3_t	origin, angles;

			if (!IntForKey(entity, "inline"))
				continue;		// not inlined, keep it as game entity

			// check the parent
//			parent = ValueForKey(entity, "parent");
//			if (strcmp(parent, parentName))
//				continue;		// current entity is not its parent

			// generate collision info?
			clipModel = ValueForKey(entity, "clipmodel");

			// get angles for rotation
			if (strcmp("", ValueForKey(entity, "angles")))
				GetVectorForKey(entity, "angles", angles);
			else {
				angles[0] = 0.0f;
				angles[1] = FloatForKey(entity, "angle");
				angles[2] = 0.0f;
			}

			angles[1] = -angles[1];		// HACK!
			AnglesToAxis(angles, axis);

			// get origin
			GetVectorForKey( entity, "origin", origin );

			model = ValueForKey( entity, "model" );
			if ( !model[0] ) {
				_printf("WARNING: func_static at %i %i %i without a model key\n", (int)origin[0],
					(int)origin[1], (int)origin[2] );
				continue;
			}

			if (ignoreClipModels && clipModel[0])
				clipModel = model;

			if ( strstr( model, ".md3" ) || strstr( model, ".MD3" ) )
				InsertMD3Model( model, origin, axis, clipModel );
			else if ( strstr( model, ".ase" ) || strstr( model, ".ASE" ) )
				InsertASEModel( model, origin, axis, clipModel );
			else if ( strstr( model, ".lwo" ) || strstr( model, ".LWO" ) )
				InsertLWOModel( model, origin, axis, clipModel );
			else
				_printf( "Unknown func_static type: %s\n", model );
		}
	}

	qprintf( "%5i triangle models\n", c_triangleModels );
	qprintf( "%5i triangle surfaces\n", c_triangleSurfaces );
	qprintf( "%5i triangle vertexes\n", c_triangleVertexes );
	qprintf( "%5i triangle indexes\n", c_triangleIndexes );
}



/*
 =======================================================================

 COLLISION SURFACE GENERATION

 =======================================================================
*/


#define CM_MAX_MAP_BOUNDS			65535


#define	MAX_TRIANGLE_FACETS	2048
#define	MAX_TRIANGLE_PLANES	16384

typedef struct {
	float	plane[4];
//	int		signBits;		// signx + (signy<<1) + (signz<<2), used as lookup during collision
} trianglePlane_t;

typedef struct {
	int			facetPlane;
	int			numBorders;		// 3 or 4 + 6 axial bevels + 4 or 3 * 4 edge bevels
	int			borderPlanes[4+6+16];
	int			borderInward[4+6+16];
} triangleFacet_t;

typedef struct triangleCollide_s {
	vec3_t	bounds[2];
	int		numPlanes;			// surface planes plus edge planes
	trianglePlane_t	*planes;
	int		numFacets;
	triangleFacet_t	*facets;
} triangleCollide_t;


typedef struct {
	int		numTris;
	vec3_t	points[SHADER_MAX_INDEXES/3][3];
} cTrisoup_t;

#define	PLANE_TRI_EPSILON	0.1


/*
=================
CM_SignbitsForNormal
=================
*//*
static int CM_SignbitsForNormal( vec3_t normal ) {
	int	bits, j;

	bits = 0;
	for (j=0 ; j<3 ; j++) {
		if ( normal[j] < 0 ) {
			bits |= 1<<j;
		}
	}
	return bits;
}
*/
/*
=====================
CM_PlaneFromPoints

Returns false if the triangle is degenrate.
The normal will point out of the clock for clockwise ordered points
=====================
*/
static qboolean CM_PlaneFromPoints( vec4_t plane, vec3_t a, vec3_t b, vec3_t c ) {
	vec3_t	d1, d2;

	VectorSubtract( b, a, d1 );
	VectorSubtract( c, a, d2 );
	CrossProduct( d2, d1, plane );
	if ( VectorNormalize( plane, plane ) == 0 ) {
		return qfalse;
	}

	plane[3] = DotProduct( a, plane );
	return qtrue;
}

/*
================================================================================

TRIANGLE COLLIDE GENERATION

================================================================================
*/

static	int				numPlanes;
static	trianglePlane_t	planes[MAX_TRIANGLE_PLANES];

static	int				numFacets;
static	triangleFacet_t	facets[MAX_TRIANGLE_PLANES]; //maybe MAX_TRIANGLE_FACETS ??

#define	NORMAL_EPSILON	0.0001
#define	DIST_EPSILON	0.02

static void Vector4Copy (vec4_t in, vec4_t out){

	out[0] = in[0];
	out[1] = in[1];
	out[2] = in[2];
	out[3] = in[3];
}

/*
==================
CM_PlaneEqual
==================
*/
static int CM_PlaneEqual(trianglePlane_t *p, float plane[4], int *flipped) {
	float invplane[4];

	if (
	   fabs(p->plane[0] - plane[0]) < NORMAL_EPSILON
	&& fabs(p->plane[1] - plane[1]) < NORMAL_EPSILON
	&& fabs(p->plane[2] - plane[2]) < NORMAL_EPSILON
	&& fabs(p->plane[3] - plane[3]) < DIST_EPSILON )
	{
		*flipped = qfalse;
		return qtrue;
	}

	invplane[0] = -plane[0];
	invplane[1] = -plane[1];
	invplane[2] = -plane[2];
	invplane[3] = -plane[3];

	if (
	   fabs(p->plane[0] - invplane[0]) < NORMAL_EPSILON
	&& fabs(p->plane[1] - invplane[1]) < NORMAL_EPSILON
	&& fabs(p->plane[2] - invplane[2]) < NORMAL_EPSILON
	&& fabs(p->plane[3] - invplane[3]) < DIST_EPSILON )
	{
		*flipped = qtrue;
		return qtrue;
	}

	return qfalse;
}

/*
==================
CM_SnapVector
==================
*/
static void CM_SnapVector(vec3_t normal) {
	int		i;

	for (i=0 ; i<3 ; i++)
	{
		if ( fabs(normal[i] - 1) < NORMAL_EPSILON )
		{
			VectorClear (normal);
			normal[i] = 1;
			break;
		}
		if ( fabs(normal[i] - -1) < NORMAL_EPSILON )
		{
			VectorClear (normal);
			normal[i] = -1;
			break;
		}
	}
}

/*
==================
CM_FindPlane2
==================
*/
static int CM_FindPlane2(float plane[4], int *flipped) {
	int i;

	// see if the points are close enough to an existing plane
	for ( i = 0 ; i < numPlanes ; i++ ) {
		if (CM_PlaneEqual(&planes[i], plane, flipped)) return i;
	}

	// add a new plane
	if ( numPlanes == MAX_TRIANGLE_PLANES ) {
		Error("MAX_TRIANGLE_PLANES" );
	}

	Vector4Copy( plane, planes[numPlanes].plane );
//	planes[numPlanes].signBits = CM_SignbitsForNormal( plane );

	numPlanes++;

	*flipped = qfalse;

	return numPlanes-1;
}

/*
==================
CM_FindPlane
==================
*/
static int CM_FindPlane( float *p1, float *p2, float *p3 ) {
	float	plane[4];
	int		i;
	float	d;

	if ( !CM_PlaneFromPoints( plane, p1, p2, p3 ) ) {
		return -1;
	}

	// see if the points are close enough to an existing plane
	for ( i = 0 ; i < numPlanes ; i++ ) {
		if ( DotProduct( plane, planes[i].plane ) < 0 ) {
			continue;	// allow backwards planes?
		}

		d = DotProduct( p1, planes[i].plane ) - planes[i].plane[3];
		if ( d < -PLANE_TRI_EPSILON || d > PLANE_TRI_EPSILON ) {
			continue;
		}

		d = DotProduct( p2, planes[i].plane ) - planes[i].plane[3];
		if ( d < -PLANE_TRI_EPSILON || d > PLANE_TRI_EPSILON ) {
			continue;
		}

		d = DotProduct( p3, planes[i].plane ) - planes[i].plane[3];
		if ( d < -PLANE_TRI_EPSILON || d > PLANE_TRI_EPSILON ) {
			continue;
		}

		// found it
		return i;
	}

	// add a new plane
	if ( numPlanes == MAX_TRIANGLE_PLANES ) {
		Error("MAX_TRIANGLE_PLANES" );
	}

	Vector4Copy( plane, planes[numPlanes].plane );
//	planes[numPlanes].signBits = CM_SignbitsForNormal( plane );

	numPlanes++;

	return numPlanes-1;
}

/*
==================
CM_PointOnPlaneSide
==================
*/
static int CM_PointOnPlaneSide( float *p, int planeNum ) {
	float	*plane;
	float	d;

	if ( planeNum == -1 ) {
		return SIDE_ON;
	}
	plane = planes[ planeNum ].plane;

	d = DotProduct( p, plane ) - plane[3];

	if ( d > PLANE_TRI_EPSILON ) {
		return SIDE_FRONT;
	}

	if ( d < -PLANE_TRI_EPSILON ) {
		return SIDE_BACK;
	}

	return SIDE_ON;
}

/*
==================
CM_TrianglePlane
==================
*/
static int	CM_TrianglePlane( int trianglePlanes[MAX_TRIANGLE_PLANES], int tri ) {
	int		p;

	p = trianglePlanes[tri];
	if ( p != -1 ) {
		return p;
	}

	// should never happen
	qprintf( "WARNING: CM_TrianglePlane unresolvable\n" );
	return -1;
}

/*
==================
CM_EdgePlaneNum
==================
*/
static int CM_EdgePlaneNum( cTrisoup_t *trisoup, int trianglePlanes[MAX_TRIANGLE_PLANES], int i, int k ) {
	float	*p1, *p2;
	vec3_t		up;
	int			p;

	switch ( k ) {
	case 0:	// top border
		p1 = trisoup->points[i][0];
		p2 = trisoup->points[i][1];
		p = CM_TrianglePlane( trianglePlanes, i);
		if (p == -1)
			return -1;
		VectorMA( p1, 4, planes[ p ].plane, up );
		return CM_FindPlane( p1, p2, up );

	case 2:	// bottom border
		p1 = trisoup->points[i][2];
		p2 = trisoup->points[i][0];
		p = CM_TrianglePlane( trianglePlanes, i);
		if (p == -1)
			return -1;
		VectorMA( p1, 4, planes[ p ].plane, up );
		return CM_FindPlane( p2, p1, up );

	case 1:	// right border
		p1 = trisoup->points[i][1];
		p2 = trisoup->points[i][2];
		p = CM_TrianglePlane( trianglePlanes, i);
		if (p == -1)
			return -1;
		VectorMA( p1, 4, planes[ p ].plane, up );
		return CM_FindPlane( p1, p2, up );
	}

	Error("CM_EdgePlaneNum: bad k" );
	return -1;
}

/*
===================
CM_SetBorderInward
===================
*/
static void CM_SetBorderInward( triangleFacet_t *facet, cTrisoup_t *trisoup, int trianglePlanes[MAX_TRIANGLE_PLANES],
						  int i, int which ) {
	int		k, l;
	float	*points[4];
	int		numPoints;

	switch ( which ) {
//	case -1:
//		points[0] = grid->points[i][j];
//		points[1] = grid->points[i+1][j];
//		points[2] = grid->points[i+1][j+1];
//		points[3] = grid->points[i][j+1];
//		numPoints = 4;
//		break;
	case 0:
		points[0] = trisoup->points[i][0];
		points[1] = trisoup->points[i][1];
		points[2] = trisoup->points[i][2];
		numPoints = 3;
		break;
	case 1:
		points[0] = trisoup->points[i][2];
		points[1] = trisoup->points[i][1];
		points[2] = trisoup->points[i][0];
		numPoints = 3;
		break;
	default:
		Error("CM_SetBorderInward: bad parameter" );
		numPoints = 0;
		break;
	}

	for ( k = 0 ; k < facet->numBorders ; k++ ) {
		int		front, back;

		front = 0;
		back = 0;

		for ( l = 0 ; l < numPoints ; l++ ) {
			int		side;

			side = CM_PointOnPlaneSide( points[l], facet->borderPlanes[k] );
			if ( side == SIDE_FRONT ) {
				front++;
			} if ( side == SIDE_BACK ) {
				back++;
			}
		}

		if ( front && !back ) {
			facet->borderInward[k] = qtrue;
		} else if ( back && !front ) {
			facet->borderInward[k] = qfalse;
		} else if ( !front && !back ) {
			// flat side border
			facet->borderPlanes[k] = -1;
		} else {
			// bisecting side border
			qprintf( "WARNING: CM_SetBorderInward: mixed plane sides\n" );
			facet->borderInward[k] = qfalse;
		}
	}
}

/*
==================
CM_ValidateFacet

If the facet isn't bounded by its borders, we screwed up.
==================
*/
static qboolean CM_ValidateFacet( triangleFacet_t *facet ) {
	float		plane[4];
	int			j;
	winding_t	*w;
	vec3_t		bounds[2];

	if ( facet->facetPlane == -1 ) {
		return qfalse;
	}

	Vector4Copy( planes[ facet->facetPlane ].plane, plane );
	w = BaseWindingForPlane( plane,  plane[3] );
	for ( j = 0 ; j < facet->numBorders && w ; j++ ) {
		if ( facet->borderPlanes[j] == -1 ) {
			return qfalse;
		}
		Vector4Copy( planes[ facet->borderPlanes[j] ].plane, plane );
		if ( !facet->borderInward[j] ) {
			VectorSubtract( vec3_origin, plane, plane );
			plane[3] = -plane[3];
		}
		ChopWindingInPlace( &w, plane, plane[3], 0.1f );
	}

	if ( !w ) {
		return qfalse;		// winding was completely chopped away
	}

	// see if the facet is unreasonably large
	WindingBounds( w, bounds[0], bounds[1] );
	FreeWinding( w );
	
	for ( j = 0 ; j < 3 ; j++ ) {
		if ( bounds[1][j] - bounds[0][j] > CM_MAX_MAP_BOUNDS ) {
			return qfalse;		// we must be missing a plane
		}
		if ( bounds[0][j] >= CM_MAX_MAP_BOUNDS ) {
			return qfalse;
		}
		if ( bounds[1][j] <= -CM_MAX_MAP_BOUNDS ) {
			return qfalse;
		}
	}
	return qtrue;		// winding is fine
}

/*
==================
CM_AddFacetBevels
==================
*/
static void CM_AddFacetBevels( triangleFacet_t *facet ) {

	int i, j, k, l;
	int axis, dir, order, flipped;
	float plane[4], d, newplane[4];
	winding_t *w, *w2;
	vec3_t mins, maxs, vec, vec2;

	Vector4Copy( planes[ facet->facetPlane ].plane, plane );

	w = BaseWindingForPlane( plane,  plane[3] );
	for ( j = 0 ; j < facet->numBorders && w ; j++ ) {
		if (facet->borderPlanes[j] == facet->facetPlane) continue;
		Vector4Copy( planes[ facet->borderPlanes[j] ].plane, plane );

		if ( !facet->borderInward[j] ) {
			VectorSubtract( vec3_origin, plane, plane );
			plane[3] = -plane[3];
		}

		ChopWindingInPlace( &w, plane, plane[3], 0.1f );
	}
	if ( !w ) {
		return;
	}

	WindingBounds(w, mins, maxs);

	// add the axial planes
	order = 0;
	for ( axis = 0 ; axis < 3 ; axis++ )
	{
		for ( dir = -1 ; dir <= 1 ; dir += 2, order++ )
		{
			VectorClear(plane);
			plane[axis] = dir;
			if (dir == 1) {
				plane[3] = maxs[axis];
			}
			else {
				plane[3] = -mins[axis];
			}
			//if it's the surface plane
			if (CM_PlaneEqual(&planes[facet->facetPlane], plane, &flipped)) {
				continue;
			}
			// see if the plane is allready present
			for ( i = 0 ; i < facet->numBorders ; i++ ) {
				if (CM_PlaneEqual(&planes[facet->borderPlanes[i]], plane, &flipped))
					break;
			}

			if ( i == facet->numBorders ) {
				if (facet->numBorders > 4 + 6 + 16) qprintf("ERROR: too many bevels\n");
				facet->borderPlanes[facet->numBorders] = CM_FindPlane2(plane, &flipped);
				facet->borderInward[facet->numBorders] = flipped;
				facet->numBorders++;
			}
		}
	}
	//
	// add the edge bevels
	//
	// test the non-axial plane edges
	for ( j = 0 ; j < w->numpoints ; j++ )
	{
		k = (j+1)%w->numpoints;
		VectorSubtract (w->p[j], w->p[k], vec);
		//if it's a degenerate edge
		if (VectorNormalize (vec, vec) < 0.5)
			continue;
		CM_SnapVector(vec);
		for ( k = 0; k < 3 ; k++ )
			if ( vec[k] == -1 || vec[k] == 1 )
				break;	// axial
		if ( k < 3 )
			continue;	// only test non-axial edges

		// try the six possible slanted axials from this edge
		for ( axis = 0 ; axis < 3 ; axis++ )
		{
			for ( dir = -1 ; dir <= 1 ; dir += 2 )
			{
				// construct a plane
				VectorClear (vec2);
				vec2[axis] = dir;
				CrossProduct (vec, vec2, plane);
				if (VectorNormalize (plane, plane) < 0.5)
					continue;
				plane[3] = DotProduct (w->p[j], plane);

				// if all the points of the facet winding are
				// behind this plane, it is a proper edge bevel
				for ( l = 0 ; l < w->numpoints ; l++ )
				{
					d = DotProduct (w->p[l], plane) - plane[3];
					if (d > 0.1)
						break;	// point in front
				}
				if ( l < w->numpoints )
					continue;

				//if it's the surface plane
				if (CM_PlaneEqual(&planes[facet->facetPlane], plane, &flipped)) {
					continue;
				}
				// see if the plane is allready present
				for ( i = 0 ; i < facet->numBorders ; i++ ) {
					if (CM_PlaneEqual(&planes[facet->borderPlanes[i]], plane, &flipped)) {
							break;
					}
				}

				if ( i == facet->numBorders ) {
					if (facet->numBorders > 4 + 6 + 16) qprintf("ERROR: too many bevels\n");
					facet->borderPlanes[facet->numBorders] = CM_FindPlane2(plane, &flipped);

					for ( k = 0 ; k < facet->numBorders ; k++ ) {
						if (facet->borderPlanes[facet->numBorders] ==
							facet->borderPlanes[k]) qprintf("WARNING: bevel plane already used\n");
					}

					facet->borderInward[facet->numBorders] = flipped;
					//
					w2 = CopyWinding(w);
					Vector4Copy(planes[facet->borderPlanes[facet->numBorders]].plane, newplane);
					if (!facet->borderInward[facet->numBorders])
					{
						newplane[0] = -newplane[0];
						newplane[1] = -newplane[1];
						newplane[2] = -newplane[2];
						newplane[3] = -newplane[3];
					} //end if
					ChopWindingInPlace( &w2, newplane, newplane[3], 0.1f );
					if (!w2) {
						qprintf("WARNING: CM_AddFacetBevels... invalid bevel\n");
						continue;
					}
					else {
						FreeWinding(w2);
					}
					//
					facet->numBorders++;
					//already got a bevel
//					break;
				}
			}
		}
	}
	FreeWinding( w );

	//add opposite plane
	facet->borderPlanes[facet->numBorders] = facet->facetPlane;
	facet->borderInward[facet->numBorders] = qtrue;
	facet->numBorders++;
}

typedef enum {
	EN_A,
	EN_B,
	EN_C
} edgeName_t;

/*
==================
CM_TriangleCollideFromTrisoup
==================
*/
static void CM_TriangleCollideFromTrisoup( cTrisoup_t *trisoup, triangleCollide_t *pf ) {
	int				i;
	float			*p1, *p2, *p3;
	int				trianglePlanes[MAX_TRIANGLE_PLANES];
	triangleFacet_t			*facet;
	int				borders[4];

	numPlanes = 0;
	numFacets = 0;

	// find the planes for each triangle of the trisoup
	for (i = 0; i < trisoup->numTris; i++){
		p1 = trisoup->points[i][0];
		p2 = trisoup->points[i][1];
		p3 = trisoup->points[i][2];
		trianglePlanes[i] = CM_FindPlane(p1, p2, p3);
	}

	// create the borders for each facet
	for ( i = 0 ; i < trisoup->numTris; i++ ) {
		borders[EN_A] = CM_EdgePlaneNum( trisoup, trianglePlanes, i, 0 );
		borders[EN_B] = CM_EdgePlaneNum( trisoup, trianglePlanes, i, 1 );
		borders[EN_C] = CM_EdgePlaneNum( trisoup, trianglePlanes, i, 2 );

		if ( numFacets == MAX_TRIANGLE_FACETS ) {
			Error("MAX_TRIANGLE_FACETS" );
		}
		facet = &facets[numFacets];
		memset( facet, 0, sizeof( *facet ) );
/*
		if ( trianglePlanes[i] == trianglePlanes[i] ) {
			if ( trianglePlanes[i] == -1 ) {
				continue;		// degenrate
			}
			facet->facetPlane = trianglePlanes[i];
			facet->numBorders = 3;
			facet->borderPlanes[0] = borders[EN_A];
			facet->borderPlanes[1] = borders[EN_B];
			facet->borderPlanes[2] = borders[EN_C];
			CM_SetBorderInward( facet, trisoup, trianglePlanes, i, -1 );
			if ( CM_ValidateFacet( facet ) ) {
				CM_AddFacetBevels( facet );
				numFacets++;
			}
		} else {*/
			// two seperate triangles
			facet->facetPlane = trianglePlanes[i];
			facet->numBorders = 3;
			facet->borderPlanes[0] = borders[EN_A];
			facet->borderPlanes[1] = borders[EN_B];
			facet->borderPlanes[2] = borders[EN_C];
			CM_SetBorderInward( facet, trisoup, trianglePlanes, i, 0 );
			if ( CM_ValidateFacet( facet ) ) {
				CM_AddFacetBevels( facet );
				numFacets++;
			}
/*
			if ( numFacets == MAX_TRIANGLE_FACETS ) {
				Error("MAX_TRIANGLE_FACETS" );
			}
			facet = &facets[numFacets];
			memset( facet, 0, sizeof( *facet ) );

			facet->facetPlane = trianglePlanes[i];
			facet->numBorders = 3;
			facet->borderPlanes[0] = borders[EN_C];
			facet->borderPlanes[1] = borders[EN_B];
			facet->borderPlanes[2] = borders[EN_A];
			CM_SetBorderInward( facet, trisoup, trianglePlanes, i, 0 );
			if ( CM_ValidateFacet( facet ) ) {
				CM_AddFacetBevels( facet );
				numFacets++;
			}
			*/
//		}
	}

	// copy the results out
	pf->numPlanes = numPlanes;
	pf->numFacets = numFacets;
	pf->facets = malloc( numFacets * sizeof( *pf->facets ));
	memcpy( pf->facets, facets, numFacets * sizeof( *pf->facets ) );
	pf->planes = malloc( numPlanes * sizeof( *pf->planes ));
	memcpy( pf->planes, planes, numPlanes * sizeof( *pf->planes ) );
}

/*
===================
CM_GenerateTriangleCollide

Creates an internal structure that will be used to perform
collision detection with a trisoup mesh.
===================
*/
static struct triangleCollide_s 	*CM_GenerateTriangleCollide( int numPoints, vec3_t *points, int numTris, int *indices ) {
	triangleCollide_t	*pf;
	cTrisoup_t		trisoup;
	int				i;

	if ( numPoints <= 2 || !points ) {
		Error("CM_GenerateTriangleFacets: bad parameters: (%i, %p)",
			numPoints, points );
	}

	// build a trisoup
	trisoup.numTris = numTris;
	for (i = 0; i < numTris; i++){
		VectorCopy(points[indices[i*3+0]], trisoup.points[i][0]);
		VectorCopy(points[indices[i*3+1]], trisoup.points[i][1]);
		VectorCopy(points[indices[i*3+2]], trisoup.points[i][2]);
	}

	// the surface defined by these points will be
	// collided against
	pf = malloc( sizeof( *pf ));
	ClearBounds( pf->bounds[0], pf->bounds[1] );
	for ( i = 0 ; i < numPoints; i++ ) {
		AddPointToBounds(points[i], pf->bounds[0], pf->bounds[1]);
	}

	// generate a bsp tree for the surface
	CM_TriangleCollideFromTrisoup( &trisoup, pf );

	// expand by one unit for epsilon purposes
	pf->bounds[0][0] -= 1;
	pf->bounds[0][1] -= 1;
	pf->bounds[0][2] -= 1;

	pf->bounds[1][0] += 1;
	pf->bounds[1][1] += 1;
	pf->bounds[1][2] += 1;

	return pf;
}




void EmitTriangleCollideForTriangleSurface (mapDrawSurface_t *ds, dsurface_t *out){

	vec3_t				temp;
	struct triangleCollide_s	*pc;
	dsurfacePlane_t	*outp;
	dsurfaceFacet_t	*outf;
	int				indices[SHADER_MAX_INDEXES];
	vec3_t			points[SHADER_MAX_VERTEXES];
	int				i, j;

	out->firstSurfacePlane = out->firstSurfaceFacet = -1;
	out->numSurfacePlanes = out->numSurfaceFacets = 0;

	if (!ds->miscModel)
		return;

	if (!ds->clipModel)
		return;

	if (ds->shaderInfo->surfaceFlags & SURFACE_NOCLIP)
		return;

	// Load the clip model.
	// This allows a low-poly version of the visible model to be used
	// for more efficient collision detection.
	if (strstr(ds->clipModelName, ".md3") || strstr(ds->clipModelName, ".MD3")){
		md3Header_t			*md3;
		md3Surface_t		*surf;
		md3Triangle_t		*tri;
		md3XyzNormal_t		*xyz;
		md3Shader_t			*shader;

		md3 = LoadModel(ds->clipModelName);
		if (!md3)
			return;

		// Find the surface
		surf = (md3Surface_t *)((byte *)md3 + md3->ofsSurfaces);
		for	(i = 0; i < md3->numSurfaces; i++){
			if (i == ds->clipModelSurface)
				break;

			// Find the next surface
			surf = (md3Surface_t *)((byte *)surf + surf->ofsEnd);
		}

		if (i == md3->numSurfaces){
			qprintf("WARNING: clip model %s has a different number of surfaces than visible model\n", ds->clipModelName);
			return;
		}

        shader = (md3Shader_t *)((byte *)surf + surf->ofsShaders);

		// Copy the indices
		tri = (md3Triangle_t *)((byte *)surf + surf->ofsTriangles);

		for (i = 0; i < surf->numTriangles; i++, tri++){
			indices[i*3+0] = tri->indexes[0];
			indices[i*3+1] = tri->indexes[1];
			indices[i*3+2] = tri->indexes[2];
		}

		// Copy the vertices
		xyz = (md3XyzNormal_t *)((byte *)surf + surf->ofsXyzNormals);

		for (i = 0; i < surf->numVerts; i++, xyz++){
			temp[0] = MD3_XYZ_SCALE * xyz->xyz[0];
			temp[1] = MD3_XYZ_SCALE * xyz->xyz[1];
			temp[2] = MD3_XYZ_SCALE * xyz->xyz[2];

			points[i][0] = DotProduct(temp, ds->clipModelAxis[0]) + ds->clipModelOrigin[0];
			points[i][1] = DotProduct(temp, ds->clipModelAxis[1]) + ds->clipModelOrigin[1];
			points[i][2] = DotProduct(temp, ds->clipModelAxis[2]) + ds->clipModelOrigin[2];
		}

		// create the internal facet structure
		pc = CM_GenerateTriangleCollide(surf->numVerts, points, surf->numTriangles, indices);
	}
	else if (strstr(ds->clipModelName, ".ase") || strstr(ds->clipModelName, ".ASE")){
		int					i, j, l;
		int					numSurfaces;
		const char			*name;
		polyset_t			*pset;
		int					numFrames;
		char				filename[1024];

		int					indexList[SHADER_MAX_INDEXES];
		int					numIndices;

		drawVert_t			vertexList[SHADER_MAX_VERTEXES], vertex;
		int					numVertices;

		sprintf( filename, "%s%s", gamedir, ds->clipModelName );

		// load the model
		ASE_Load( filename, qfalse, qfalse );

		// Find the surface
		numSurfaces = ASE_GetNumSurfaces();

		for (i = 0; i < numSurfaces; i++){
			if (i == ds->clipModelSurface)
				break;
		}

		if (i == numSurfaces){
			qprintf("WARNING: clip model %s has a different number of surfaces than visible model\n", ds->clipModelName);
			return;
		}

		name = ASE_GetSurfaceName( i );

		pset = ASE_GetSurfaceAnimation( i, &numFrames, -1, -1, -1 );
		if ( !name || !pset ) {
			return;
		}

		// Copy vertices
		numIndices = 0;
		numVertices = 0;

		for ( j = 0 ; j < pset->numtriangles * 3 ; j++ ) {
			int		index;
			triangle_t	*tri;

			index = j % 3;
			tri = &pset->triangles[ j / 3 ];

			vertex.xyz[0] = tri->verts[index][0];
			vertex.xyz[1] = tri->verts[index][1];
			vertex.xyz[2] = tri->verts[index][2];

			vertex.st[0] = tri->texcoords[index][0];
			vertex.st[1] = tri->texcoords[index][1];

			// Add it to the vertex list if not added yet
			if (numIndices == SHADER_MAX_INDEXES){
				printf("SHADER_MAX_INDEXES hit\n");
				return;
			}

			for (l = 0; l < numVertices; l++){
				if (vertexList[l].xyz[0] != vertex.xyz[0] || vertexList[l].xyz[1] != vertex.xyz[1] || vertexList[l].xyz[2] != vertex.xyz[2])
					continue;
				if (vertexList[i].st[0] != vertex.st[0] || vertexList[i].st[1] != vertex.st[1])
					continue;

				break;
			}

			if (l == numVertices){
				if (numVertices == SHADER_MAX_VERTEXES){
					printf("SHADER_MAX_VERTEXES hit\n");
					return;
				}

				indexList[numIndices++] = numVertices;
				vertexList[numVertices++] = vertex;
			}
			else
				indexList[numIndices++] = l;
		}

		// Copy the indices
		for (j = 0; j < numIndices; j += 3){
			indices[j+0] = indexList[j+0];
			indices[j+1] = indexList[j+1];
			indices[j+2] = indexList[j+2];
		}

		// Copy the vertices
		for (j = 0; j < numVertices; j++){
			points[j][0] = DotProduct(vertexList[j].xyz, ds->clipModelAxis[0]) + ds->clipModelOrigin[0];
			points[j][1] = DotProduct(vertexList[j].xyz, ds->clipModelAxis[1]) + ds->clipModelOrigin[1];
			points[j][2] = DotProduct(vertexList[j].xyz, ds->clipModelAxis[2]) + ds->clipModelOrigin[2];
		}

		// create the internal facet structure
		pc = CM_GenerateTriangleCollide(numVertices, points, numIndices / 3, indices);
	}
	else if (strstr(ds->clipModelName, ".lwo") || strstr(ds->clipModelName, ".LWO")){
		lwObject			*inObject;
		lwLayer				*inLayer;
		lwSurface			*inSurface;
		lwPolygon			*inPolygon;
		lwPolVert			*inPolVert;
		lwPoint				*inPoint;
		lwVMapPt			*inVMapPt;
		int					defaultSTAxis[2];
		float				defaultXYZ2STScale[2];
		float				min, max, size, st[2];
		unsigned			failId;
		int					failPos;
		int					i, j, k, l;

		int					indexList[SHADER_MAX_INDEXES];
		int					numIndices;

		drawVert_t			vertexList[SHADER_MAX_VERTEXES], vertex;
		int					numVertices;

		char				filename[1024];

		sprintf( filename, "%s%s", gamedir, ds->clipModelName );

		// Load the file
		inObject = lwGetObject(filename, &failId, &failPos);
		if (!inObject)
			return;

		if (inObject->nlayers != 1)
			return;

		inLayer = &inObject->layer[0];

		// Setup default ST map
		defaultSTAxis[0] = 0;
		defaultSTAxis[1] = 1;

		st[0] = 0.0f;
		st[1] = 0.0f;

		for (i = 0; i < 3; i++){
			min = inLayer->bbox[i+0];
			max = inLayer->bbox[i+3];

			size = max - min;

			if (size > st[0]){
				defaultSTAxis[1] = defaultSTAxis[0];
				defaultSTAxis[0] = i;

				st[1] = st[0];
				st[0] = size;
			}
			else if (size > st[1]){
				defaultSTAxis[1] = i;

				st[1] = size;
			}
		}

		defaultXYZ2STScale[0] = 4.0f / st[0];
		defaultXYZ2STScale[1] = 4.0f / st[1];

		// Find the surface
		inSurface = inObject->surf;

		for (i = 0; i < inObject->nsurfs; i++){
			if (i == ds->clipModelSurface)
				break;

			// Find the next surface
			inSurface = inSurface->next;
		}

		if (i == inObject->nsurfs){
			qprintf("WARNING: clip model %s has a different number of surfaces than visible model\n", ds->clipModelName);
			return;
		}

		// Copy vertices
		numIndices = 0;
		numVertices = 0;

		for (j = 0, inPolygon = inLayer->polygon.pol; j < inLayer->polygon.count; j++, inPolygon++){
			if (inPolygon->surf != inSurface)
				continue;

			if (inPolygon->type != ID_FACE){
				qprintf("WARNING: polygon type != ID_FACE, discarded...\n");
				continue;
			}

			if (inPolygon->nverts != 3){
				qprintf("WARNING: polygon has %i vertices, discarded...\n", inPolygon->nverts);
				continue;
			}

			for (k = 0, inPolVert = inPolygon->v; k < 3; k++, inPolVert++){
				inPoint = &inLayer->point.pt[inPolVert->index];

				vertex.xyz[0] = inPoint->pos[0];
				vertex.xyz[1] = inPoint->pos[2];
				vertex.xyz[2] = inPoint->pos[1];

				vertex.st[0] = vertex.xyz[defaultSTAxis[0]] * defaultXYZ2STScale[0];
				vertex.st[1] = vertex.xyz[defaultSTAxis[1]] * defaultXYZ2STScale[1];

				for (l = 0, inVMapPt = inPoint->vm; l < inPoint->nvmaps; l++, inVMapPt++){
					if (inVMapPt->vmap->type == LWID_('T', 'X', 'U', 'V')){
						vertex.st[0] = inVMapPt->vmap->val[inVMapPt->index][0];
						vertex.st[1] = 1.0f - inVMapPt->vmap->val[inVMapPt->index][1];
					}
				}

				for (l = 0, inVMapPt = inPolVert->vm; l < inPolVert->nvmaps; l++, inVMapPt++){
					if (inVMapPt->vmap->type == LWID_('T', 'X', 'U', 'V')){
						vertex.st[0] = inVMapPt->vmap->val[inVMapPt->index][0];
						vertex.st[1] = 1.0f - inVMapPt->vmap->val[inVMapPt->index][1];
					}
				}

				// Add it to the vertex list if not added yet
				if (numIndices == SHADER_MAX_INDEXES){
					printf("SHADER_MAX_INDEXES hit\n");
					return;
				}

				for (l = 0; l < numVertices; l++){
					if (vertexList[l].xyz[0] != vertex.xyz[0] || vertexList[l].xyz[1] != vertex.xyz[1] || vertexList[l].xyz[2] != vertex.xyz[2])
						continue;
					if (vertexList[i].st[0] != vertex.st[0] || vertexList[i].st[1] != vertex.st[1])
						continue;

					break;
				}

				if (l == numVertices){
					if (numVertices == SHADER_MAX_VERTEXES){
						printf("SHADER_MAX_VERTEXES hit\n");
						return;
					}

					indexList[numIndices++] = numVertices;
					vertexList[numVertices++] = vertex;
				}
				else
					indexList[numIndices++] = l;
			}
		}

		// Copy the indices
		for (j = 0; j < numIndices; j += 3){
			indices[j+0] = indexList[j+0];
			indices[j+1] = indexList[j+1];
			indices[j+2] = indexList[j+2];
		}

		// Copy the vertices
		for (j = 0; j < numVertices; j++){
			points[j][0] = DotProduct(vertexList[j].xyz, ds->clipModelAxis[0]) + ds->clipModelOrigin[0];
			points[j][1] = DotProduct(vertexList[j].xyz, ds->clipModelAxis[1]) + ds->clipModelOrigin[1];
			points[j][2] = DotProduct(vertexList[j].xyz, ds->clipModelAxis[2]) + ds->clipModelOrigin[2];
		}

		lwFreeObject(inObject);

		// create the internal facet structure
		pc = CM_GenerateTriangleCollide(numVertices, points, numIndices / 3, indices);
	}
	else {
		if (!ds->terrain)
			return;

		// Copy the indices
		for (i = 0; i < ds->numIndexes; i += 3){
			indices[i+0] = ds->indexes[i+0];
			indices[i+1] = ds->indexes[i+1];
			indices[i+2] = ds->indexes[i+2];
		}

		// Copy the vertices
		for (i = 0; i < ds->numVerts; i++){
			points[i][0] = ds->verts[i].xyz[0];
			points[i][1] = ds->verts[i].xyz[1];
			points[i][2] = ds->verts[i].xyz[2];
		}

		// create the internal facet structure
		pc = CM_GenerateTriangleCollide(ds->numVerts, points, ds->numIndexes / 3, indices);
	}

	// Emit the collision info
	out->firstSurfacePlane = numSurfacePlanes;
	out->numSurfacePlanes = pc->numPlanes;
	out->firstSurfaceFacet = numSurfaceFacets;
	out->numSurfaceFacets = pc->numFacets;

	for (i = 0; i < pc->numPlanes; i++){
		if (numSurfacePlanes == MAX_MAP_SURFACEPLANES)
			Error("MAX_MAP_SURFACEPLANES");

		outp = &dsurfacePlanes[numSurfacePlanes];
		numSurfacePlanes++;

		outp->plane[0] = pc->planes[i].plane[0];
		outp->plane[1] = pc->planes[i].plane[1];
		outp->plane[2] = pc->planes[i].plane[2];
		outp->plane[3] = pc->planes[i].plane[3];
	}

	for (i = 0; i < pc->numFacets; i++){
		if (numSurfaceFacets == MAX_MAP_SURFACEFACETS)
			Error("MAX_MAP_SURFACEFACETS");

		outf = &dsurfaceFacets[numSurfaceFacets];
		numSurfaceFacets++;

		outf->facetPlane = pc->facets[i].facetPlane;
		outf->numBorders = pc->facets[i].numBorders;
		outf->borderInward = 0;
		
		for (j = 0; j < 4+6+16; j++){
			outf->borderPlanes[j] = pc->facets[i].borderPlanes[j];

			// To save space, we pack these into a single integer
			if (pc->facets[i].borderInward[j])
				outf->borderInward |= (1<<j);
		}
	}
}
